import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-07-24
 * Time: 7:52
 */
public class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int[] res = new int[spells.length];
        for (int i = 0; i < spells.length; i++) {
            int left = 0, right = potions.length - 1;
            // 初始值为 数组的长度而不是 -1
            int index = potions.length;
            // 二分查找, 找到最接近的值的下标
            while (left <= right) {
                int mid = (right - left) / 2 + left;
                // 这里注意这个 spells[i]  类型是 long
                if ((long)spells[i] * potions[mid] >= success) {
                    right = mid - 1;
                    // 更新最接近的值的下标
                    index = mid;
                } else {
                    left = mid + 1;
                }
            }
            res[i] = potions.length - index;
        }
        return res;
    }
}

